`:top
`!Multi-objective linear programming`! is a subarea of `F33f`_`[mathematical optimization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mathematical_optimization]`_`f. A multiple objective linear program (MOLP) is a `F33f`_`[linear program`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linear_program]`_`f with more than one objective function. An MOLP is a special case of a vector linear program. Multi-objective linear programming is also a subarea of `F33f`_`[Multi-objective optimization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multi-objective_optimization]`_`f.
>>Contents
• `F0af`_`[Problem formulation`#problem-formulation]`_`f
• `F0af`_`[Solution concepts`#solution-concepts]`_`f
• `F0af`_`[Solution methods`#solution-methods]`_`f
• `F0af`_`[Related problem classes`#related-problem-classes]`_`f
• `F0af`_`[References`#references]`_`f
-─
>>Problem formulation
In mathematical terms, a MOLP can be written as:
min x P x s.t. a ≤ ≤ B x ≤ ≤ b , ℓ ℓ ≤ ≤ x ≤ ≤ u {\\displaystyle \\min _{x}Px\\quad {\\text{s.t.}}\\quad a\\leq Bx\\leq b,\\;\\ell \\leq x\\leq u}
where B {\\displaystyle B} is an ( m × × n ) {\\displaystyle (m\\times n)} matrix, P {\\displaystyle P} is a ( q × × n ) {\\displaystyle (q\\times n)} matrix, a {\\displaystyle a} is an m {\\displaystyle m} -dimensional vector with components in R ∪ ∪ { − − ∞ ∞ } {\\displaystyle \\mathbb {R} \\cup \\{-\\infty \\}} , b {\\displaystyle b} is an m {\\displaystyle m} -dimensional vector with components in R ∪ ∪ { + ∞ ∞ } {\\displaystyle \\mathbb {R} \\cup \\{+\\infty \\}} , ℓ ℓ {\\displaystyle \\ell } is an n {\\displaystyle n} -dimensional vector with components in R ∪ ∪ { − − ∞ ∞ } {\\displaystyle \\mathbb {R} \\cup \\{-\\infty \\}} , u {\\displaystyle u} is an n {\\displaystyle n} -dimensional vector with components in R ∪ ∪ { + ∞ ∞ } {\\displaystyle \\mathbb {R} \\cup \\{+\\infty \\}}
>>Solution concepts
A feasible point x {\\displaystyle x} is called `*efficient`* if there is no feasible point y {\\displaystyle y} with P x ≤ ≤ P y {\\displaystyle Px\\leq Py} , P x ≠ ≠ P y {\\displaystyle Px\\neq Py} , where ≤ ≤ {\\displaystyle \\leq } denotes the component-wise ordering.
Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....`:cite-ref-eckerkouada1978-1-0[`F5bf`_`[1`#cite-note-eckerkouada1978-1]`_`f] There are also algorithms to determine the set of all maximal efficient faces.`:cite-ref-eckerhegner1980-2-0[`F5bf`_`[2`#cite-note-eckerhegner1980-2]`_`f] Based on these goals, the set of all efficient (extreme) points can be seen to be the solution of MOLP. This type of solution concept is called `*decision set based`*.`:cite-ref-benson1998-3-0[`F5bf`_`[3`#cite-note-benson1998-3]`_`f] It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).
Efficient points are frequently called `*efficient solutions`*. This term is misleading because a single efficient point can be already obtained by solving one linear program, such as the linear program with the same feasible set and the objective function being the sum of the objectives of MOLP.`:cite-ref-ehrgott2015-4-0[`F5bf`_`[4`#cite-note-ehrgott2015-4]`_`f]
More recent references consider `*outcome set based`* solution concepts`:cite-ref-heydel-hne2011-5-0[`F5bf`_`[5`#cite-note-heydel-hne2011-5]`_`f] and corresponding algorithms.`:cite-ref-dauersaleh1990-6-0[`F5bf`_`[6`#cite-note-dauersaleh1990-6]`_`f]`:cite-ref-benson1998-3-1[`F5bf`_`[3`#cite-note-benson1998-3]`_`f] Assume MOLP is bounded, i.e. there is some y ∈ ∈ R q {\\displaystyle y\\in \\mathbb {R} ^{q}} such that y ≤ ≤ P x {\\displaystyle y\\leq Px} for all feasible x {\\displaystyle x} . A solution of MOLP is defined to be a finite subset S ¯ ¯ {\\displaystyle {\\bar {S}}} of efficient points that carries a sufficient amount of information in order to describe the `*upper image`* of MOLP. Denoting by S {\\displaystyle S} the feasible set of MOLP, the `*upper image`* of MOLP is the set P := P [ S ] + R + q := { y ∈ ∈ R q : ∃ ∃ x ∈ ∈ S : y ≥ ≥ P x } {\\displaystyle {\\mathcal {P}}:=P[S]+\\mathbb {R} _{+}^{q}:=\\{y\\in \\mathbb {R} ^{q}:\\;\\exists x\\in S:y\\geq Px\\}} . A formal definition of a solution `:cite-ref-heydel-hne2011-5-1[`F5bf`_`[5`#cite-note-heydel-hne2011-5]`_`f]`:cite-ref-l-hne2011-7-0[`F5bf`_`[7`#cite-note-l-hne2011-7]`_`f] is as follows:
A finite set S ¯ ¯ {\\displaystyle {\\bar {S}}} of efficient points is called `*solution`* to MOLP if conv P [ S ¯ ¯ ] + R + q = P {\\displaystyle \\operatorname {conv} P[{\\bar {S}}]+\\mathbb {R} _{+}^{q}={\\mathcal {P}}} ("conv" denotes the convex hull).
If MOLP is not bounded, a solution consists not only of points but of points and directions `:cite-ref-l-hne2011-7-1[`F5bf`_`[7`#cite-note-l-hne2011-7]`_`f]`:cite-ref-l-hnewei-ing2017-8-0[`F5bf`_`[8`#cite-note-l-hnewei-ing2017-8]`_`f]
>>Solution methods
Multiobjective variants of the `F33f`_`[simplex algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Simplex_algorithm]`_`f are used to compute decision set based solutions`:cite-ref-eckerkouada1978-1-1[`F5bf`_`[1`#cite-note-eckerkouada1978-1]`_`f]`:cite-ref-eckerhegner1980-2-1[`F5bf`_`[2`#cite-note-eckerhegner1980-2]`_`f]`:cite-ref-armandmalivert1991-9-0[`F5bf`_`[9`#cite-note-armandmalivert1991-9]`_`f] and objective set based solutions.`:cite-ref-rudloffulus2016-10-0[`F5bf`_`[10`#cite-note-rudloffulus2016-10]`_`f]
Objective set based solutions can be obtained by `F33f`_`[Benson's algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Benson's_algorithm]`_`f.`:cite-ref-benson1998-3-2[`F5bf`_`[3`#cite-note-benson1998-3]`_`f]`:cite-ref-l-hnewei-ing2017-8-1[`F5bf`_`[8`#cite-note-l-hnewei-ing2017-8]`_`f]
>>Related problem classes
Multiobjective linear programming is equivalent to `F33f`_`[polyhedral`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Polyhedral_combinatorics]`_`f projection.`:cite-ref-l-hnewei-ing2016-11-0[`F5bf`_`[11`#cite-note-l-hnewei-ing2016-11]`_`f]
>>References
`:cite-note-eckerkouada1978-1`!1.`! `F0af`_`[↑`#cite-ref-eckerkouada1978-1-0]`_`f `:citerefeckerkouada1978`aEcker, J. G.; Kouada, I. A. (1978). "Finding all efficient extreme points for multiple objective linear programs". `*Mathematical Programming`*. `!14`! (1): 249–261. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/BF01588968. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0025-5610. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 42726689.
`:cite-note-eckerhegner1980-2`!2.`! `F0af`_`[↑`#cite-ref-eckerhegner1980-2-0]`_`f `:citerefeckerhegnerkouada1980`aEcker, J. G.; Hegner, N. S.; Kouada, I. A. (1980). "Generating all maximal efficient faces for multiple objective linear programs". `*Journal of Optimization Theory and Applications`*. `!30`! (3): 353–381. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/BF00935493. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0022-3239. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 120455645.
`:cite-note-benson1998-3`!3.`! `F0af`_`[↑`#cite-ref-benson1998-3-0]`_`f `:citerefbenson1998`aBenson, Harold P. (1998). "An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem". `*Journal of Global Optimization`*. `!13`! (1): 1–24. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1023/A:1008215702611. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0925-5001. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 45440728.
`:cite-note-ehrgott2015-4`!4.`! `F0af`_`[↑`#cite-ref-ehrgott2015-4-0]`_`f `:citerefehrgott2005`aEhrgott, M. (2005). `*Multicriteria Optimization`*. Springer. `F33f`_`[CiteSeerX`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=CiteSeerX_(identifier)]`_`f 10.1.1.360.5223. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/3-540-27659-9. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-3-540-21398-7.
`:cite-note-heydel-hne2011-5`!5.`! `F0af`_`[↑`#cite-ref-heydel-hne2011-5-0]`_`f `:citerefheydel-hne2011`aHeyde, Frank; Löhne, Andreas (2011). "Solution concepts in vector optimization: a fresh look at an old story" (PDF). `*Optimization`*. `!60`! (12): 1421–1440. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1080/02331931003665108. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0233-1934. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 54519405.
`:cite-note-dauersaleh1990-6`!6.`! `F0af`_`[↑`#cite-ref-dauersaleh1990-6-0]`_`f `:citerefdauersaleh1990`aDauer, J.P.; Saleh, O.A. (1990). "Constructing the set of efficient objective values in multiple objective linear programs". `*European Journal of Operational Research`*. `!46`! (3): 358–365. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/0377-2217(90)90011-Y. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0377-2217.
`:cite-note-l-hne2011-7`!7.`! `F0af`_`[↑`#cite-ref-l-hne2011-7-0]`_`f `:citerefl-hne2011`aLöhne, Andreas (2011). `*Vector Optimization with Infimum and Supremum`*. Vector Optimization. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/978-3-642-18351-5. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-3-642-18350-8. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 1867-8971.
`:cite-note-l-hnewei-ing2017-8`!8.`! `F0af`_`[↑`#cite-ref-l-hnewei-ing2017-8-0]`_`f `:citerefl-hnewei-ing2017`aLöhne, Andreas; Weißing, Benjamin (2017). "The vector linear program solver Bensolve – notes on theoretical background". `*European Journal of Operational Research`*. `!260`! (3): 807–813. `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:1510.04823. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/j.ejor.2016.02.039. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0377-2217. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 17267946.
`:cite-note-armandmalivert1991-9`!9.`! `F0af`_`[↑`#cite-ref-armandmalivert1991-9-0]`_`f `:citerefarmandmalivert1991`aArmand, P.; Malivert, C. (1991). "Determination of the efficient set in multiobjective linear programming". `*Journal of Optimization Theory and Applications`*. `!70`! (3): 467–489. `F33f`_`[CiteSeerX`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=CiteSeerX_(identifier)]`_`f 10.1.1.161.9730. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/BF00941298. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0022-3239. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 18407847.
`:cite-note-rudloffulus2016-10`!10.`! `F0af`_`[↑`#cite-ref-rudloffulus2016-10-0]`_`f `:citerefrudloffulusvanderbei2016`aRudloff, Birgit; Ulus, Firdevs; Vanderbei, Robert (2016). "A parametric simplex algorithm for linear vector optimization problems". `*Mathematical Programming`*. `!163`! (1–2): 213–242. `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:1507.01895. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/s10107-016-1061-z. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0025-5610. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 13844342.
`:cite-note-l-hnewei-ing2016-11`!11.`! `F0af`_`[↑`#cite-ref-l-hnewei-ing2016-11-0]`_`f `:citerefl-hnewei-ing2016`aLöhne, Andreas; Weißing, Benjamin (2016). "Equivalence between polyhedral projection, multiple objective linear programming and vector linear programming". `*Mathematical Methods of Operations Research`*. `!84`! (2): 411–426. `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:1507.00228. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/s00186-016-0554-0. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 1432-2994. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 26137201.
`c`F0af`_`[↑ Back to top`#top]`_`f`a